#[test]
fn test_wiggle_sort() {
    let mut nums = vec![2, 3, 1 ,3 ,4, 1];
    wiggle_sort(&mut nums);
    println!("{:?}", nums);
}

pub fn wiggle_sort(nums: &mut Vec<i32>) {
    let mut arr = nums.clone();
    arr.sort();
    let n = nums.len();
    let x = (nums.len() + 1) / 2;
    let (mut i, mut j, mut k) = (0, x-1, n-1);
    while i < n {
        nums[i] = arr[j];
        if i+1 < n {
            nums[i+1] = arr[k];
        }
        i += 2;
        if i < n {  // avoid subtract overflow
            k -= 1;
            j -= 1;
        }
    }
}